package vip.george.p0004;

import java.util.Arrays;

public class P4 {


    /**
     * 暴力解法：
     * 遍历两个数组，将两个数组合并成一个数组，然后对数组进行排序，然后取中位数
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int mergeLen = len1 + len2;
        int[] newArray = new int[mergeLen];
        for (int i = 0; i < len1; i++) {
            newArray[i] = nums1[i];
        }
        for (int i = 0; i < len2; i++) {
            newArray[len1 + i] = nums2[i];
        }
        //排序
        Arrays.sort(newArray);
        if (mergeLen % 2 == 0) {
            return (newArray[mergeLen / 2 - 1] + newArray[mergeLen / 2]) / 2.0;
        } else {
            return newArray[mergeLen / 2];
        }
    }

    /**
     * 暴力解法：
     * 遍历两个数组，将两个数组的元素添加到一个新的数组中（添加的时候就排序）， 然后取中位数
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int mergeLen = len1 + len2;
        int[] newArray = new int[mergeLen];
        int p1 = 0;
        int p2 = 0;
        int p = 0;
        while (p < mergeLen) {
            if (p1 < len1 && p2 == len2) {
                newArray[p] = nums1[p1];
                p1++;
            }
            if (p2 < len2 && p1 == len1) {
                newArray[p] = nums2[p2];
                p2++;
            }
            if (p1 < len1 && p2 < len2) {
                if (nums1[p1] < nums2[p2]) {
                    newArray[p] = nums1[p1];
                    p1++;
                } else {
                    newArray[p] = nums2[p2];
                    p2++;
                }
            }
            p++;
            // System.out.println(Arrays.toString(newArray));
        }
        if (mergeLen % 2 == 0) {
            return (newArray[mergeLen / 2 - 1] + newArray[mergeLen / 2]) / 2.0;
        } else {
            return newArray[mergeLen / 2];
        }
    }

    public static void main(String[] args) {
        P4 p = new P4();
        System.out.println(p.findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4}));
        System.out.println(p.findMedianSortedArrays(new int[]{1, 3}, new int[]{2}));
        System.out.println(p.findMedianSortedArrays(new int[]{0, 0}, new int[]{0, 0}));
    }
}
